A Hash table is a data structure with a highly efficient lookup, which store key values pairs. Each key is generated by a **hash function** based on the value being stored. Also, the hash table has to handle **collisions** that happens when the same key is generated for different values.

```typescript
  [1]
  [2] = ["A"] // value A store in the key 2
  [3]
  [4] = ["B"] 
```

Whenever we need to retrieve a value we use its **key**, so this operation will be done in a constant time, considering that a good hash function is being used and the values are uniformly distributed across the hash table, which means fewer collisions. Inserting a value into a hash table, is pretty straightforward, just generate the key, and use it to find the right position in the hash table.

### A basic hash function

A hash function should be easy to compute because it will be used whenever is necessary to insert or search a value, also this function has to provide uniform distribution across the hash table in order to avoid clustering which would affect the hash table performance.

For this example, our hash table will store strings, so the hash function will sum the ASCII values of each character, then it will divide that sum by the size of the hash table and get the reminder using the modulo operator (%), the result will be the key.

```typescript
// hash function
hash(value: string): number {
  const sum = value
      .split("")
      .reduce((acc: number, char: string) => acc + char.charCodeAt(0), 0);

  // force sum into the hash table size
  return sum % this.size;
}
```

### How to handle collisions

Collisions happen when the same key is generated for different values, a common strategy to handle collisions is **Separate chaining:**, instead of storing the value directly in the hash table, we store it in a [Linked List](/data-structures-in-typescript-linked-list), and the generated key points to that Linked list. If there were too many collisions, searching a value would take a linear time complexity O(n) instead of O(1), this time can be reduced to O(log n) using another data structure like a [Binary Search Tree](/data-structures-in-typescript-binary-search-tree).

```typescript
[1]
[2] = ["A"] ->
[3]
[4] = ["B"] -> ["C"] -> ["D"] -> // collisions happened, so these 3 values are in the same linked list
```

### Implementation

Here is an implementation of a Hash Table in TypeScript

```typescript
class HashTable {
  private size: number;
  private data: LinkedList<string>[] = [];

  constructor(size: number) {
    this.size = size;
  }

  hash(value: string): number {
    const sum = value
      .split("")
      .reduce((acc: number, char: string) => acc + char.charCodeAt(0), 0);

    // force sum into the hash table size
    return sum % this.size;
  }

  insert(value: string): void {
    const index = this.hash(value);

    if (!this.data[index]) {
      this.data[index] = new LinkedList<string>(
        (a: string, b: string) => a === b
      );
    }

    this.data[index].append(value);
  }

  search(value: string): string | null {
    const index = this.hash(value);

    if (this.data[index]) {
      return this.data[index].search(value)!.data;
    }

    return null;
  }
}

const hashTable = new HashTable(10);

hashTable.insert("aabb");
hashTable.insert("bbcc");
hashTable.insert("abcd");

console.log(hashTable.search("abcd"));
```


A Hash table is a data structure with a highly efficient lookup, which store key values pairs

Data Structures in TypeScript - Hash Table

This is one of those problems that have properties that, given an example, we can identify them right away, like "_check if this array is ordered_", if it contains only a few elements we just have to look at it and we will know.

Before we continue, if necessary, take some time to understand what is a BST reading [this post](https://ricardoborges.dev/data-structures-in-typescript-binary-search-tree).

For example, look at this Binary tree:

![binary tree](https://res.cloudinary.com/dje4crtui/image/upload/v1626722908/data%20structures/tree/bst_yeac5b.png)

You know this is a BST because it satisfy the definition: `left.data <= current.data < right.data`.

So far, we understand the problem and we can identify a BST just looking at it, what is pending now, is the algorithm. Basically, all we have to do is check if every subtree satisfies the definition of the BST, let's see how we would do that.

- Starting with the **root node**, well that node can have any value, in this case, **5**;
- Moving on to the left child node **2**, now this node can't be greater than its parent (**5**);
- Node **2**'s left child **1** also has a limit (**2**);
- Node **2**'s right child **3** must have a value that is greater than its parent (**2**) but less than 5.

Up until now, we have noticed that some node has to be between a minimum and maximum value. Left nodes don't have a minimum constraint, and the root node doesn't have any constraints at all.

- Now moving to the right subtree, the root node's right child **7**, has to be greater than its parent;
- Node **7**'s right child **8** must be greater than **7**;
- Node **7**'s left child **6** must be between **5** and **7**.

Now we know that both subtrees have similar constraints, with this information, we know that our algorithm will start with the root node and will check if some nodes are between some **min** and **max** values, while other nodes don't have a **min** or **max** limit:

```typescript
function isBST(node: BinarySearchTreeNode<number>, min: number, max: number) {}
```

We can do this recursively, so we need a base case:

```typescript
function isBST(node: BinarySearchTreeNode<number>, min: number, max: number) {
  if (!node) return true; // base case
}
```

Next step is to check if the current node, is between those **min** and **max** values, we also have to consider that some nodes don't have those constraints, so we can expect that **min** and **max** can be _null_:

```typescript
function isBST(node: BinarySearchTreeNode<number>, min: number, max: number) {
  if (!node) return true; // base case

  if ((min && node.data <= min) || (max && node.data > max)) {
    return false;
  }
}
```

Finally, we have to do the same for left and right subtrees, if any of them don't satisfy the BST definition we simply return _false_

```typescript
function isBST(node: BinarySearchTreeNode<number>, min: number, max: number) {
  if (!node) return true; // base case

  if ((min && node.data <= min) || (max && node.data > max)) {
    return false;
  }

  // if the right or the left subtree is not a BST, return false
  if (
    !isBST(node.leftNode, min, node.data) ||
    !isBST(node.rightNode, node.data, max)
  ) {
    return false;
  }

  // finally, if all subtrees are under those constraints, return true
  return true;
}
```

That's it, I tried to explain step by step this algorithm, I hope I succeed.


Checking if a Binary Tree is a BST step by step

How to check if a Binary Tree is a BST

### What is a Tree data structure

Before we talk BST, we have to understand that a tree is a kind of [Graph](https://ricardoborges.dev/data-structures-in-typescript-graph) with a root node and no cycles, each node can have zero or more child nodes, nodes can store any type of data, also those nodes may or may not be in a particular order, nodes that have no children are called leaves.

![tree](https://res.cloudinary.com/dje4crtui/image/upload/v1626722908/data%20structures/tree/tree_sgyxim.png)

### Binary Tree

A Binary tree is a tree that each node has up to two nodes:

![binary tree](https://res.cloudinary.com/dje4crtui/image/upload/v1627406718/data%20structures/tree/binary-tree_uunege.png)

### Binary Search Tree

A BST is a Binary tree that follows these properties:

- All left descendants nodes are less or equal to their parent node
- All right descendants nodes are greater than their parent node

![binary search tree](https://res.cloudinary.com/dje4crtui/image/upload/v1626722908/data%20structures/tree/bst_yeac5b.png)

BST definitions can slightly vary, you may find a BSTs that the left subtree is less than the parent node (`left subtree < parent <= right subtree`).

Also, some BSTs may or may not allow duplicated nodes.

BST is useful when you need to insert, delete and search comparable elements. You can use an array for those operations, but, although access an element in an array is done in a constant time, whenever you insert or delete an element, the other elements have to be shifted, in a BST, on the other hand, you only need to adjust the pointers.

### Searching in the BST

The search starts from the root node, if the element you are searching for is greater than the current node value, then search for it in the right subtree, otherwise search in the left subtree, repeat this until the current node value is equal to the element you are searching for or until you reach a leaf node and there is nowhere to go:

```typescript
search(data) {
    // empty tree
    if (!root) return;

    // start from root node
    let current = root;

    while (current.data !== data) {
        // data greater than current element
        if (data > current.data) {

        // you are on a leaf node, nowhere to go
        if (!current.rightNode) return;

        // go to the right subtree
        current = current.rightNode;
        } else {

        // you are on a leaf node, nowhere to go
        if (!current.leftNode) return;

        // go to the left subtree
        current = current.leftNode;
        }
    }

    return current;
}
```

### Inserting in the BST

When inserting a new element in BST you have to keep its properties, so start from the root node, if the new element value is greater than the root node value, search for an empty position in the right subtree, otherwise search for an empty position in the left subtree:

```typescript
insert(data) {
  // empty tree, insert the first node (the root node)
  if (!root) {
    root = new Node(data);
    return root;
  }

  // start from the root node
  let current = root;

  while (true) {
    if (data > current.data) {
      // search for an empty position in the right subtree
      if (current.rightNode) {
        current = current.rightNode;
      } else {
        // insert node
        current.rightNode = new Node(data);
        return current.rightNode;
      }
    } else {
      // search for an empty position in the left subtree
      if (current.leftNode) {
        current = current.leftNode;
      } else {
        // insert node
        current.leftNode = new Node(data);
        return current.leftNode;
      }
    }
  }
}

```

### Binary Search Tree traversal

There are three ways to traverse a BST, they differ on which order the nodes are visited (often, printed):

#### In-Order traversal

First visit left branch, then the current node, and finally the right branch, because of how elements are distributed in the BST, they will be visited in the ascending order:

```typescript
inOrderTraversal(node) {
  if (node) {
    inOrderTraversal(node.leftNode);
    console.log(node.data);
    inOrderTraversal(node.rightNode);
  }
}
```

#### Pre-Order traversal

Visit the current node before its children:

```typescript
preOrderTraversal(node) {
  if (node) {
    console.log(node.data);
    this.preOrderTraversal(node.leftNode);
    this.preOrderTraversal(node.rightNode);
  }
}
```

#### Post-Order traversal

Visit the current node's children first, then the current node:

```typescript
postOrderTraversal(node) {
  if (node) {
    this.postOrderTraversal(node.leftNode);
    this.postOrderTraversal(node.rightNode);
    console.log(node.data);
  }
}
```

Here's an implementation of a BST in typescript:

```typescript
export class BinarySearchTreeNode<T> {
  data: T;
  leftNode?: BinarySearchTreeNode<T>;
  rightNode?: BinarySearchTreeNode<T>;

  constructor(data: T) {
    this.data = data;
  }
}

export class BinarySearchTree<T> {
  root?: BinarySearchTreeNode<T>;
  comparator: (a: T, b: T) => number;

  constructor(comparator: (a: T, b: T) => number) {
    this.comparator = comparator;
  }

  insert(data: T): BinarySearchTreeNode<T> | undefined {
    if (!this.root) {
      this.root = new BinarySearchTreeNode(data);
      return this.root;
    }

    let current = this.root;

    while (true) {
      if (this.comparator(data, current.data) === 1) {
        if (current.rightNode) {
          current = current.rightNode;
        } else {
          current.rightNode = new BinarySearchTreeNode(data);
          return current.rightNode;
        }
      } else {
        if (current.leftNode) {
          current = current.leftNode;
        } else {
          current.leftNode = new BinarySearchTreeNode(data);
          return current.leftNode;
        }
      }
    }
  }

  search(data: T): BinarySearchTreeNode<T> | undefined {
    if (!this.root) return undefined;

    let current = this.root;

    while (this.comparator(data, current.data) !== 0) {
      if (this.comparator(data, current.data) === 1) {
        if (!current.rightNode) return;

        current = current.rightNode;
      } else {
        if (!current.leftNode) return;

        current = current.leftNode;
      }
    }

    return current;
  }

  inOrderTraversal(node: BinarySearchTreeNode<T> | undefined): void {
    if (node) {
      this.inOrderTraversal(node.leftNode);
      console.log(node.data);
      this.inOrderTraversal(node.rightNode);
    }
  }

  preOrderTraversal(node: BinarySearchTreeNode<T> | undefined): void {
    if (node) {
      console.log(node.data);
      this.preOrderTraversal(node.leftNode);
      this.preOrderTraversal(node.rightNode);
    }
  }

  postOrderTraversal(node: BinarySearchTreeNode<T> | undefined): void {
    if (node) {
      this.postOrderTraversal(node.leftNode);
      this.postOrderTraversal(node.rightNode);
      console.log(node.data);
    }
  }
}

function comparator(a: number, b: number) {
  if (a < b) return -1;

  if (a > b) return 1;

  return 0;
}

const bst = new BinarySearchTree(comparator);

bst.insert(5);

bst.insert(2);
bst.insert(3);
bst.insert(1);

bst.insert(7);
bst.insert(6);
bst.insert(8);

bst.inOrderTraversal(bst.root);
```

Unlike Graphs, a tree doesn't really need a Tree class, just a Node class would usually suffice.


Binary Search Trees are useful when you need to insert, delete and search comparable elements.

Data Structures in Typescript - Binary Search Tree

Topological sort is an ordering of the vertices of a directed acyclic graph, in a way that if there is an edge from a vertex A to B, then A comes before B. For example, let's say there is a set of projects and some of them depend on other projects:

![graph](https://res.cloudinary.com/dje4crtui/image/upload/v1625769510/data%20structures/top_sort_q7iaub.png)

In this example project B and C depends on project A, and project D depends on projects B and C. Therefore, project A must be executed first, then projects B and C, and finally project D. Resulting in this order: [A, B, C, D] or [A, C, B, D].

Note that we start from node A because it doesn't have dependencies and repeat it, that is after A is done, B and C haven't dependencies anymore, so we can choose either one to be the next. That's why this algorithm works only on acyclic graphs.

We can use a modified depth-first search for this algorithm, [here I talk more about DPS](https://ricardoborges.dev/data-structures-in-typescript-graph). The steps are the following:

1 - For every unvisited node visit it and its adjacent nodes (DPS)
2 - After visiting a node and its adjacent add it at the beginning of a list (you can use a stack instead), this list will be in the topological order.

Here's an implementation in TypeScript, I'm using [this implementation of a graph](https://ricardoborges.dev/data-structures-in-typescript-graph):

```typescript
function topSort(
  node: Node<number>,
  visited: Map<number, boolean>,
  order: number[]
) {
  if (!node) return;

  // set node as visited
  visited.set(node.data, true);

  // for each of node's unvisited adjacent call topSort
  node.adjacent.forEach((item) => {
    if (!visited.has(item.data)) {
      topSort(item, visited, order);
    }
  });

  // add node at the beginning of the order list
  order.unshift(node.data);
}

// topological order list
const order = [];
// map to keep track of visited nodes
const visited = new Map();

// For every unvisited node visit it and its adjacent nodes
for (const entry of graph.nodes.entries()) {
  const node = entry[1];
  if (!visited.has(node.data)) {
    topSort(node, visited, order);
  }
}
```

There are other problems that topological sorting can resolve, like the order that courses have to be selected during college, since they may have other courses as a prerequisite. Or even the order of steps of a recipe, in which some must be taken before others.

There are a lot of explanations for this algorithm on the internet, here I tried to explain it in a little different way, I hope this helped you to make sense of it or if you haven't heard about topological sorting before, at least this may be an introduction of it.


Topological sort is an ordering of the vertices of a directed acyclic graph, in a way that if there is an edge from a vertex A to B, then A comes before B.

Topological sort

The graph is a data structure that consists of vertices (or nodes) that can be connected to other vertices by edges.

![graph](https://res.cloudinary.com/dje4crtui/image/upload/v1623451532/data%20structures/graph_1_w9efdw.png)

The **degree** is the number of edges that are connected to a vertex, for example, the vertex **A** has a degree of **1** and the vertex **C** has a degree of 2.

Graphs can either directed or undirected, directed graphs are like a one-way street, undirected is like a two-way street.

![directed and undirected graphs](https://res.cloudinary.com/dje4crtui/image/upload/v1623367833/data%20structures/graph_2_tzprzz.png)

Graphs can also have cycles.

![cyclic and acyclic graphs](https://res.cloudinary.com/dje4crtui/image/upload/v1623367833/data%20structures/graph_3_v0zmhu.png)

Graphs might be a disconnected one, that means it consists of isolated subgraphs, or a connected one, in which all every pair of nodes are connected by an edge.

![connected and disconnected graphs](https://res.cloudinary.com/dje4crtui/image/upload/v1623367833/data%20structures/graph_4_eujwdh.png)

Graphs can be used to represent networks, websites structure, also used in path optimization algorithms, there are applications in other fields, such as linguistics, physics, chemistry, biology, mathematics, etc.

### Representation

Graphs can be represented with

- **Adjacency list** - Every node stores a list of adjacent vertices, for example, an array or that contains all vertices and each vertex contains another array with adjacent vertices, other data structures can be used instead of an array, like a hash table and a linked list.

- **Adjacency matrix** - An NxN boolean matrix (where N is the number of vertices), if the matrix[i][j] stores the value true, there is a connection between the vertices i and j. In an undirected graph matrix[j][i] also will store the value true. You can use other types instead of boolean, for example, numbers to represent weight.

![adjacency list and matrix](https://res.cloudinary.com/dje4crtui/image/upload/v1623367833/data%20structures/graph_5_qpznlu.png)

### Graph Search

#### Depth-first search

Depth-first search is a way to navigate a graph, it starts from a given vertex and visits each branch completely before moving to another branch. DFS is often used when we need to visit every node in the graph.

![graph depth-first search](https://res.cloudinary.com/dje4crtui/image/upload/v1623451532/data%20structures/graph_6_pr8wqq.png)

Using DPS on the graph above the nodes will be visited in the following order: A, B, D, C, E, F.

#### Breadth-first search

This is another way to navigate a graph, it starts from a given vertex and visits all adjacent vertices before go to any of their children. BFS is useful to find a path between two nodes.

![graph breadth-first search](https://res.cloudinary.com/dje4crtui/image/upload/v1623451532/data%20structures/graph_6_pr8wqq.png)

Using DPS on the graph above the nodes will be visited in the following order: A, B, E, F, D, C.

#### Bidirectional search

Consists of running two breadth-first searches simultaneously, each one starts from a different vertex and runs until they collide. This is useful to find the shortest path between two vertices.

![Bidirectional search](https://res.cloudinary.com/dje4crtui/image/upload/v1623452079/data%20structures/graph_7_yzwhhf.png)

Heres an implementation of a directed graph using a adjacency list, because it will perform better in almost all operations:

```typescript
export class Node<T> {
  data: T;
  adjacent: Node<T>[];
  comparator: (a: T, b: T) => number;

  constructor(data: T, comparator: (a: T, b: T) => number) {
    this.data = data;
    this.adjacent = [];
    this.comparator = comparator;
  }

  addAdjacent(node: Node<T>): void {
    this.adjacent.push(node);
  }

  removeAdjacent(data: T): Node<T> | null {
    const index = this.adjacent.findIndex(
      (node) => this.comparator(node.data, data) === 0
    );

    if (index > -1) {
      return this.adjacent.splice(index, 1)[0];
    }

    return null;
  }
}

class Graph<T> {
  nodes: Map<T, Node<T>> = new Map();
  comparator: (a: T, b: T) => number;

  constructor(comparator: (a: T, b: T) => number) {
    this.comparator = comparator;
  }

  /**
   * Add a new node if it was not added before
   *
   * @param {T} data
   * @returns {Node<T>}
   */
  addNode(data: T): Node<T> {
    let node = this.nodes.get(data);

    if (node) return node;

    node = new Node(data, this.comparator);
    this.nodes.set(data, node);

    return node;
  }

  /**
   * Remove a node, also remove it from other nodes adjacency list
   *
   * @param {T} data
   * @returns {Node<T> | null}
   */
  removeNode(data: T): Node<T> | null {
    const nodeToRemove = this.nodes.get(data);

    if (!nodeToRemove) return null;

    this.nodes.forEach((node) => {
      node.removeAdjacent(nodeToRemove.data);
    });

    this.nodes.delete(data);

    return nodeToRemove;
  }

  /**
   * Create an edge between two nodes
   *
   * @param {T} source
   * @param {T} destination
   */
  addEdge(source: T, destination: T): void {
    const sourceNode = this.addNode(source);
    const destinationNode = this.addNode(destination);

    sourceNode.addAdjacent(destinationNode);
  }

  /**
   * Remove an edge between two nodes
   *
   * @param {T} source
   * @param {T} destination
   */
  removeEdge(source: T, destination: T): void {
    const sourceNode = this.nodes.get(source);
    const destinationNode = this.nodes.get(destination);

    if (sourceNode && destinationNode) {
      sourceNode.removeAdjacent(destination);
    }
  }

  /**
   * Depth-first search
   *
   * @param {T} data
   * @param {Map<T, boolean>} visited
   * @returns
   */
  private depthFirstSearchAux(node: Node<T>, visited: Map<T, boolean>): void {
    if (!node) return;

    visited.set(node.data, true);

    console.log(node.data);

    node.adjacent.forEach((item) => {
      if (!visited.has(item.data)) {
        this.depthFirstSearchAux(item, visited);
      }
    });
  }

  depthFirstSearch() {
    const visited: Map<T, boolean> = new Map();
    this.nodes.forEach((node) => {
      if (!visited.has(node.data)) {
        this.depthFirstSearchAux(node, visited);
      }
    });
  }

  /**
   * Breadth-first search
   *
   * @param {T} data
   * @returns
   */
  private breadthFirstSearchAux(node: Node<T>, visited: Map<T, boolean>): void {
    const queue: Queue<Node<T>> = new Queue();

    if (!node) return;

    queue.add(node);
    visited.set(node.data, true);

    while (!queue.isEmpty()) {
      node = queue.remove();

      if (!node) continue;

      console.log(node.data);

      node.adjacent.forEach((item) => {
        if (!visited.has(item.data)) {
          visited.set(item.data, true);
          queue.add(item);
        }
      });
    }
  }

  breadthFirstSearch() {
    const visited: Map<T, boolean> = new Map();
    this.nodes.forEach((node) => {
      if (!visited.has(node.data)) {
        this.breadthFirstSearchAux(node, visited);
      }
    });
  }
}

function comparator(a: number, b: number) {
  if (a < b) return -1;

  if (a > b) return 1;

  return 0;
}

const graph = new Graph(comparator);
```


Graphs can be used to represent networks, websites structure, path optimization algorithms, there are also applications in other fields.

Data Structures in TypeScript - Graph

A queue uses FIFO (first-in-first-out) ordering, that is, items are removed from the queue in the same order that they are added, like a line.
Queues can be used whenever is necessary to process things in that order (FIFO), like requests to a single shared resource, CPU scheduling, also helps in algorithms of other data structures, such as breadth-first search in graphs.

![queue](https://res.cloudinary.com/dje4crtui/image/upload/v1622906544/data%20structures/queue_dw6rf8.png)

### Representation

A queue can be implemented using an array or a linked list, can be either fixed or dynamic size.

### Basic operations

- **Add** - Add an item to the end of the queue, also called enqueue.
- **Remove** - Remove the first item from the queue, also called dequeue.
- **Peek** - Return the top of the queue, without removing it.
- **isEmpty** - Return true if the queue is empty.
- **isFull** - Return true if the stack is full, used when the queue is fixed size.

Here's an implementation of a queue using an array, in TypeScript an array doesn't have a fixed length, so the operation **isFull** is not required, however, you can implement a queue with a fixed length and use that operation.

```typescript
class Queue<T> {
  private array: T[] = [];

  add(data: T): void {
    this.array.push(data);
  }

  remove(): T | undefined {
    if (this.isEmpty()) throw new EmptyQueueException();

    return this.array.shift();
  }

  peek(): T {
    if (this.isEmpty()) throw new EmptyQueueException();

    return this.array[0];
  }

  isEmpty(): boolean {
    return this.array.length === 0;
  }
}
```


Queues can be used whenever is necessary to process things in a first-in-first-out order, also helps in algorithms of other data structures.

Data Structures in TypeScript - Queue

A stack uses LIFO (last-in-first-out) ordering, the most recent item added is the first item to be removed, just like a real stack.
Some uses of this data structure are expressions evaluations and conversion (prefix, postfix, and infix), backtracking, and memory management.

![stack](https://res.cloudinary.com/dje4crtui/image/upload/v1622906576/data%20structures/stack_rccvuz.png)

### Representation

A stack can be implemented using an array or a linked list, can be either fixed or dynamic size.

### Basic operations

- **Push** - Add an item to the top of the stack
- **Pop** - Remove the top item from the stack
- **Peek** - Return the top of the stack, without removing it.
- **isEmpty** - Return true if the stack is empty.
- **isFull** - Return true if the stack is full, used when the stack is fixed size.

Here's an implementation of a stack using an array, in TypeScript an array doesn't have a fixed length, so the operation **isFull** is not required, however, you can implement a stack with a fixed length and use that operation.

```typescript
class Stack<T> {
  private array: T[] = [];

  pop(): T | undefined {
    if (this.isEmpty()) throw new EmptyStackException();

    return this.array.pop();
  }

  push(data: T): void {
    this.array.push(data);
  }

  peek(): T {
    if (this.isEmpty()) throw new EmptyStackException();

    return this.array[this.array.length - 1];
  }

  isEmpty(): boolean {
    return this.array.length === 0;
  }
}
```


You can use stacks for expressions evaluations and conversion, backtracking, and memory management.

Data Structures in TypeScript - Stack

A linked list is a data structure that holds objects arranged in a linear order, this order is determined by a pointer in each node.
Unlike an array, a linked list doesn't provide constant-time access to a particular index, you have to iterate through the list to find an element, on the other hand, is possible to add and remove items from the beginning of the list in a constant time.
Linked lists can be used to implement other data structures, such as stacks, queues, and graphs.

There are some types of linked lists: 

* **Singly linked list** - Each node has only a pointer to the next node. 
* **Doubly linked list** - Each node has pointers to both the previous and next node. 
* **Circular linked list** - The last node points to the first element.

### Representation

![linked list](https://res.cloudinary.com/dje4crtui/image/upload/v1622906568/data%20structures/linked-list_jdtg7y.png)

- **Head** - the first node
- **Tail** - the last node

### Basic operations

**Insertion** - It's possible to insert a new element anywhere in the list, you just have to take care of the pointers. If you are adding an element to the beginning the new node will pointer to the former head node. If you are appending to the tail, the former tail node will point to the new node. Now, if inserting between nodes, the previous node has to point to the new node which will point to the next node

**Deletion** - Follow a similar logic of insertion, if you want to remove a node from the middle of the list, you just have to make the target's previous node point to the target's next node. In a doubly-linked list, you have to take care of the previous pointer too.

**Traverse** - Each node has a point to next, so you start from the node head and follow the pointers until the last node, which will not point to any node (in a non-circular linked list)

```typescript
n = list.head

while n != null
    n = n.next

```

Here's an implementation of a singly linked list:

```typescript
class Node<T> {
  data: T;
  next: Node<T> | null = null;

  constructor(data: T) {
    this.data = data;
  }
}

class LinkedList<T> {
  head: Node<T> | null = null;
  comparator: (a: T, b: T) => boolean;

  constructor(comparator: (a: T, b: T) => boolean) {
    this.comparator = comparator;
  }

  append(data: T): void {
    if (!this.head) {
      this.head = new Node(data);
    } else {
      let current = this.head;
      while (current.next != null) {
        current = current.next;
      }
      current.next = new Node(data);
    }
  }

   delete(data: T): void {
    if (!this.head) return;

    // Check if the head node is the node to be removed
    if (this.comparator(this.head.data, data)) {
      this.head = this.head.next;
      return;
    }

    let current = this.head.next;
    let previous = this.head;

    /**
     * Search for the node to be removed and keep track of its previous node
     *
     * If it were a double linked list, we could simply search the node
     * and it would have a pointer to the previous node
     **/
    while (current) {
      if (this.comparator(current.data, data)) {
        current = null;
      } else {
        previous = current;
        current = current.next;
      }
    }

    /**
     * set previous.next to the target.next, if the node target is not found,
     * the 'previous' will point to the last node,
     * since the last node hasn't next, nothing will happen
     **/
    previous.next = previous.next ? previous.next.next : null;
  }

  search(data: T): Node<T> | null {
    let current = this.head;
    while (current) {
      if (this.comparator(current.data, data)) {
        return current;
      }
      current = current.next;
    }
    return null;
  }

  traverse() {
    let current = this.head;
    while (current != null) {
      console.log(current.data);
      current = current.next;
    }
  }
}
```

### Runner technique

This technique consists in iterate through a linked list with two pointers, a slow and a fast which will be ahead of the slow pointer by *n* nodes.

![runner technique](https://res.cloudinary.com/dje4crtui/image/upload/v1622906568/data%20structures/runner_kkvdx4.png)

This is useful to solve some problems with a linked list, like detecting a cycle or finding the middle node of a linked list when you don't know its size.

```typescript
/** Finding the middle node of a linked list **/

let slow: LinkedListNode<number> | null | undefined = linkedList.head;
let fast: LinkedListNode<number> | null | undefined = linkedList.head?.next;

/**
 * The "fast" will move twice as fast as the "slow" one,
 * so at the moment the "fast" reaches the end of the list,
 * the "slow" will be in the middle of the list
 **/

while (fast) {
  slow = slow?.next;
  fast = fast?.next?.next;
}

console.log(slow);
```


Linked Lists have some advantages over arrays and can be used to implement other data structures, such as stacks, queues, and graphs.

Data Structures in TypeScript - Linked List

An array is a common data structure that holds items of the same type, in TypeScript, unlike other languages, an array doesn't have a fixed length. Also, in TypeScript, you don't have to re-organize all elements of an array when makings operations like insert or delete.

### Representation

![array](https://res.cloudinary.com/dje4crtui/image/upload/v1622593241/array-img_kn9hp3.png)

* **Elements** are the items stored in an array
* **Index** is the location of an element in an array, it goes from 0 to (array length - 1)


```typescript
/** An array can be written like this **/

const numbers: number[] = [1, 2, 3, 4]
const names = string[] = ['Snake', 'Ocelot', 'Otacon', 'Naomi']

/** Also can be written using a generic array type, Array<elemType> **/

let list: Array<number> = [1, 2, 3, 4]
let list: Array<string> = ['Snake', 'Ocelot', 'Otacon', 'Naomi']
```

### Basics operations

**Traverse** - Print all array items one by one

```typescript
/** 3 ways to iterate an array **/

for(let i=0; i<array.length; i++) {
    console.log(array[i])
}

for(const item of array) {
    console.log(item)
}

array.forEach(item => {
    console.log(item)
})
```

**Insertion** - Add an item

```typescript
/** add to the end **/
array.push(5)

/** add to the beginning **/
array.unshift(0)

/** add in a specific index position **/
array.splice(3, 0, 8) // add 8 in the index 3
```

**Deletion** - Remove an item

```typescript
/** remove from the end **/
array.pop()

/** remove from the beginning **/
array.shift()

/** remove from a specific index position **/
array.splice(2, 1) // remove from index 2
```

**Update** - Update an item

```typescript
/** update element in position 1 **/
array[1] = 7
```

**Search** - Search by an item

```typescript
/** you can traverse an array to find an element by its value, or simply use the .find() function **/

const item = array.find(item => item === 3) // search by an item with value 3
```

### Strings are arrays of characters

All above operations can be performed on strings to solve problems like count the occurrences of a character in a string:

```typescript
let str = "aabbccdd"
let occurrences = 0

for(let i=0; i < str.length; i++) {
    if(str[i] === "c") {
        occurrences++
    }
}

console.log(occurrences) // prints 2
```

An array is a common data structure that holds items of the same type, in TypeScript, unlike other languages, an array doesn't have a fixed length.

Ricardo Borges